It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable 2-coloring of (...) pairs admits a pair of low₂ infinite homogeneous sets whose degrees form a minimal pair. (shrink)

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...) in general. We also answer the analogs of two well-known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply COH or WKL 0 in the context of reverse mathematics. (shrink)

An abstract mathematical theory is presented for a common variety of soritical arguments, treated here in terms of responses of a system, say, a biological organism, a gadget, or a set of normative linguistic rules, to stimuli. Any characteristic of the system's responses which supervenes on stimuli is called a stimulus effect upon the system. Classificatory sorites is about the identity of or difference between the effects of stimuli that differ 'only microscopically'. We formulate the classificatory sorites on arguably the (...) highest possible level of generality and show that the 'paradox' is dissolved on grounds unrelated to vague predicates or other linguistic issues traditionally associated with it. If stimulus effects are properly defined (i.e., they are uniquely determined by stimuli), and if the space of the stimuli is endowed with appropriate (not necessarily metric) closeness and connectedness properties, then this space must contain points in every vicinity of which, 'however small', the stimulus effect is not constant. The effects can only be 'tolerant' to very small differences between stimuli if the closeness structure that is used to define very close stimuli does not render the space of stimuli appropriately connected: in this case the 'paradox' cannot be formulated. Nor can it be formulated if the response properties considered are not true effects, i.e., if they do not supervene on stimuli. (shrink)

Sorites is an ancient piece of paradoxical reasoning pertaining to sets with the following properties: elements of the set are mapped into some set of “attributes”; if an element has a given attribute then so are the elements in some vicinity of this element; and such vicinities can be arranged into pairwise overlapping finite chains connecting two elements with different attributes. Obviously, if Superveneince is assumed, then Tolerance implies lack of Connectedness, and Connectedness implies lack of Tolerance. Using a very (...) general but precise definition of “vicinity”, Dzhafarov & Dzhafarov offered two formalizations of these mutual contrapositions. Mathematically, the formalizations are equally valid, but in this paper, we offer a different basis by which to compare them. Namely, we show that the formalizations have different proof-theoretic strengths when measured in the framework of reverse mathematics: the formalization of is provable in$RC{A_0}$, while the formalization of is equivalent to$AC{A_0}$over$RC{A_0}$. Thus, in a certain precise sense, the approach of is more constructive than that of. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] between two (...) principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [math] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [math], uncovering new differences between their logical strengths. (shrink)

We develop a mathematical theory for comparative sorites, considered in terms of a system mapping pairs of stimuli into a binary response characteristic whose values supervene on stimulus pairs and are interpretable as the complementary relations 'are the same' and 'are not the same' (overall or in some respect). Comparative sorites is about hypothetical sequences of stimuli in which every two successive elements are mapped into the relation 'are the same', while the pair comprised of the first and the last (...) elements of the sequence is mapped into 'are not the same'. Although soritical sequences of this kind are logically possible, we argue that their existence is grounded in no empirical evidence and show that it is excluded by a certain psychophysical principle proposed for human comparative judgements in a context unrelated to soritical issues. We generalize this principle to encompass all conceivable situations for which comparative sorites can be formulated. (shrink)

In many simple integral domains, such as Z or Z[i], there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like Z[x] or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show (...) how to computably extend Z in such a way that we can control the ordinary integer primes in any Π20 way, all while maintaining unique factorization. As a corollary, we establish the existence of a computable unique factorization domain such that the set of primes is Π20-complete in every computable presentation. (shrink)

We formulate a polarized version of Ramsey’s theorem for trees. For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs, the situation is more complex. In particular, there are many reasonable notions of stability in the tree setting, complicating the analysis of the related results.